package main

import (
	"fmt"
)

func main() {
	nums := []int{1,4,4,21,6,8,9,8,76,54,5,3}
	fmt.Printf("排序之后 nums=%v \n", sortArray(nums))
	
}

func sortArray(nums []int) []int {
	fmt.Println("详细的说明什么是堆排序\n 首先我们可以根据堆的特性，即大顶堆顶是最大的元素，小顶堆顶是最小的元素，每一个父节点都要比子节点大或者小\n根据这样的特性, 可以把整个数组看做是一棵数, 然后把它每一层调整成一个堆即可\n我们需要从这个树的最后一个父节点从上到下的进行堆处理\n每次我们需要判断当前父节点和子节点三个之间大小的对比，按照大或者小的规则，进行调整")
	fmt.Printf("调整之后，每次取得的第一个元素就是最大或者最小的，将它放入结果集\n")
	fmt.Printf("然后可以将其放入堆的最后一位，并且对0 ~ n-1之间的数据进行堆化之后重复上述步骤\n")
	fmt.Printf("直到最后一个元素都已经排完了，结束整个排序\n")
	fmt.Printf("排序之前 nums=%v \n", nums)
	return HeapSort(nums)
}

func HeapSort(nums []int) []int {
	res := make([]int, len(nums))
	edge := len(nums)
	lastP := len(nums)/2 - 1
	for i := lastP; i >= 0; i-- {
		adjustHeap(nums, i, edge)
	}

	//fmt.Println(nums)
	//当前的数组就变成一个小根堆的状态
	for i := 0; i < len(nums); i++ {
		res[i] = nums[0]
		nums[0], nums[edge-1] = nums[edge-1], nums[0]
		edge--
		adjustHeap(nums, 0, edge)
		//fmt.Println(nums, res)
	}

	return res
}

//这个的参数分别是
// -- 1.需要进行排序的数据
// -- 2.需要处理的一个父节点
// -- 3.边界
func adjustHeap(nums []int, index, edge int) {
	left, right := index*2+1, index*2+2
	minIndex := index //
	if left < edge && nums[left] < nums[minIndex] {
		minIndex = left
	}

	if right < edge && nums[right] < nums[minIndex] {
		minIndex = right
	}

	if minIndex != index {
		nums[minIndex], nums[index] = nums[index], nums[minIndex]
		adjustHeap(nums, minIndex, edge)
	}
}
